"""
问题是：给定一个任意常规（非分形）单连通平面图形，平分其面积的直线构成一个直线族，该直线族会具备什么样的特征？
这个答案较为复杂，可以确定的是，当且仅当图像中心对称时，直线族交于一点。
但对于不交于一点的图像，如何描述直线族的特征？
思路是这样的：
每个角度有且只有一条面积平分线，以 delta 间隔设置不同角度分别采样，然后求相邻直线的交点
然后 delta -> 0，这些交点就会渐渐收敛于一条曲线，直线族的直线均与该曲线相切
"""

import math

import matplotlib.pyplot as plt
import numpy as np


def polygon_area(poly):
    """多边形面积（Shoelace公式）。"""
    x = np.array([p[0] for p in poly])
    y = np.array([p[1] for p in poly])
    if poly[0] != poly[-1]:
        x = np.append(x, x[0])
        y = np.append(y, y[0])
    return 0.5 * np.sum(x[:-1] * y[1:] - x[1:] * y[:-1])


def clip_polygon_halfspace(poly, n, t):
    """Sutherland–Hodgman 裁剪：保留 n·x <= t 的半平面部分。"""

    def inside(p): return n[0] * p[0] + n[1] * p[1] - t <= 1e-12

    def intersection(p1, p2):
        d = (p2[0] - p1[0], p2[1] - p1[1])
        denom = n[0] * d[0] + n[1] * d[1]
        if abs(denom) < 1e-15: return p1
        a = (t - (n[0] * p1[0] + n[1] * p1[1])) / denom
        return (p1[0] + a * d[0], p1[1] + a * d[1])

    if not poly: return []
    out, prev, prev_in = [], poly[-1], inside(poly[-1])
    for curr in poly:
        cur_in = inside(curr)
        if cur_in:
            if not prev_in:
                out.append(intersection(prev, curr))
            out.append(curr)
        elif prev_in:
            out.append(intersection(prev, curr))
        prev, prev_in = curr, cur_in
    return out


def bisect_offset(poly, n, total_area):
    """求使面积平分的截距 t。"""
    dots = [n[0] * p[0] + n[1] * p[1] for p in poly]
    lo, hi = min(dots) - 5.0, max(dots) + 5.0
    target = total_area / 2.0
    for _ in range(60):
        mid = 0.5 * (lo + hi)
        clipped = clip_polygon_halfspace(poly, n, mid)
        a = abs(polygon_area(clipped)) if clipped else 0.0
        if a < target: lo = mid
        else: hi = mid
    return 0.5 * (lo + hi)


def compute_envelope(poly, n_samples=720):
    """给定多边形 poly，计算平分线族的包络曲线点集。"""
    A_tot = abs(polygon_area(poly))
    thetas = np.linspace(0, math.pi, n_samples, endpoint=False)
    ts = np.empty_like(thetas)
    for i, th in enumerate(thetas):
        n = (math.cos(th), math.sin(th))
        ts[i] = bisect_offset(poly, n, A_tot)
    dth = thetas[1] - thetas[0]
    tp = np.gradient(ts, dth, edge_order=2)
    xs = ts * np.cos(thetas) + tp * (-np.sin(thetas))
    ys = ts * np.sin(thetas) + tp * (np.cos(thetas))
    return xs, ys


def plot_shape_and_envelope(poly, title=""):
    xs, ys = compute_envelope(poly)
    plt.figure(figsize=(7, 7))
    poly_x = [p[0] for p in poly] + [poly[0][0]]
    poly_y = [p[1] for p in poly] + [poly[0][1]]
    plt.plot(poly_x, poly_y, 'k-', linewidth=2, label="Input shape")
    plt.plot(xs, ys, 'r-', linewidth=2, label="Envelope")
    plt.gca().set_aspect('equal', adjustable='box')
    plt.legend()
    plt.title(title)
    plt.show()


# ------------------------------
# Demo 1: 正三角形
# ------------------------------
s = 2.0
h = s * math.sqrt(3) / 2
triangle = [(-s / 2, -h / 3), (s / 2, -h / 3), (0, 2 * h / 3)]
plot_shape_and_envelope(triangle, "Equilateral Triangle")

# ------------------------------
# Demo 2: 椭圆 (用多边形采样近似)
# ------------------------------
ellipse = [(2 * math.cos(t), 1 * math.sin(t)) for t in np.linspace(0, 2 * math.pi, 400)]
plot_shape_and_envelope(ellipse, "Ellipse (2x1)")

# ------------------------------
# Demo 3: 抛物线 y=1-x^2 与直线 y=0 构成的区域
# ------------------------------
x_vals = np.linspace(-1, 1, 400)
parabola = [(x, 1 - x ** 2) for x in x_vals]
line = [(1, 0), (-1, 0)]
region = parabola + line
plot_shape_and_envelope(region, "Region between y=1-x^2 and y=0")


"""
问题：
给定一个常规（非分形）、单连通的有限面积平面图形，所有“平分面积”的直线构成一个直线族，这个直线族具有什么特征？
结论 1（交于一点的情况）：
当且仅当图形是 中心对称（180°旋转对称） 时，所有平分线必定交于该中心点。典型例子：圆、椭圆、矩形、平行四边形。
结论 2（非中心对称的情况）：
对一般图形：
每个方向角 θ\theta 存在且仅存在一条面积平分线；
于是可以把平分线族参数化为 ℓ(θ):n(θ)⋅x=t(θ)\ell(\theta): n(\theta)\cdot x = t(\theta)。
思路：
1. 取有限间隔 Δθ\Delta\theta，对每个角度采样得到平分线；
2. 求相邻两条平分线的交点；
3. 当 Δθ→0\Delta\theta \to 0，交点集合收敛到一条 包络曲线；
4. 从微分几何角度可证明：这条曲线的参数方程是
    X(θ)=t(θ) n(θ)+t′(θ) n⊥(θ),X(\theta) = t(\theta)\,n(\theta) + t'(\theta)\,n^\perp(\theta), 
    它正是所有平分线的公共包络；
5. 因此，非中心对称情形下，平分线族并不会交于一点，而是构成一族对某条 包络曲线相切 的直线。

这样描述，就把**“交于一点” ⇔ 中心对称** 和 “否则 ⇒ 与一条曲线相切” 区分清楚了。
"""